package middle;

public class Solution_86 {

    public ListNode partition(ListNode head, int x) {
        ListNode pre = null, nodePre = null, node = head, targetNode, rst = null;
        while (node!=null) {
            if (node.val >= x) {
                break;
            }
            pre = node;
            if (rst == null) {
                rst = pre;
            }
            node = node.next;
        }
        targetNode = node;
        rst = rst == null ? node : rst;

        while (node != null) {
            if (node.val < x) {
                // swap
                if (pre == null) {
                    pre = node;
                    node = node.next;
                    pre.next = targetNode;
                    rst = pre;
                } else {
                    pre.next = node;
                    node = node.next;
                    pre = pre.next;
                    pre.next = targetNode;
                }
                nodePre.next = node;
            } else {
                nodePre = node;
                node = node.next;
            }
        }
        return rst;
    }

    public static void main(String[] args) {
        Solution_86 model = new Solution_86();
        ListNode header = new ListNode(1);
        header.next = new ListNode(4);
        header.next.next = new ListNode(3);
        header.next.next.next = new ListNode(2);
        header.next.next.next.next = new ListNode(5);
        header.next.next.next.next.next = new ListNode(2);
        ListNode rst = model.partition(header, 0);
        System.out.println();
    }

    static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
